\documentclass{article}
\usepackage{hyperref}
\usepackage{listings}
\usepackage{enumerate}
\usepackage{algorithmic}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{mdwlist}
\usepackage{graphicx}
\usepackage[boldfont,slantfont,CJKaddspaces]{xeCJK}
\punctstyle{kaiming} %标点压缩风格
\setCJKmainfont{AR PL SungtiL GB}
\renewcommand{\baselinestretch}{1.40}
\lstset{language=C++}%这条命令可以让LaTeX排版时将C++键字突出显示
\lstset{breaklines}%这条命令可以让LaTeX自动将长的代码行换行排版
\lstset{extendedchars=false}%这一条命令可以解决代码跨页时，章节标题，页眉等汉字不显示的问题
\lstset{numbers=left} %添加行号
\hypersetup{colorlinks=true,linkcolor=black,citecolor=blue}

\title{ucore-vfs支持FAT32实验报告}
\date{}
\author{渠准 2008011322 计82}
\begin{document}
\maketitle
\newpage
\tableofcontents
\newpage
\section{实验目标描述}
\begin{enumerate}[(1)]
\item 在原有文件系统基础上添加一个FAT32格式的img，同时让ucore的vfs能同时支持FAT32和原有的sfs，进行文件读写等操作。
\item 添加shell下一些指令，如cp，diff等，便于检测。
\end{enumerate}

\section{组员}
\begin{itemize*}
\item 任胜韦，前期一起参与框架的搭建，在第七周的时候被分配了其他的任务，故而退出了本项目。
\item 渠准，前期一起参与框架的搭建，第七周之后继续完成了框架的实现等。此外，这份文档也是由渠准完成的。
\end{itemize*}

\section{工作进展}
如下叙述每周的工作进展，更详细地可参见\href{http://code.google.com/p/u9proj/w/list}{这里}。
\begin{enumerate*}
\item\emph{12th$\scriptsize{\sim}$18th March 2011} 查阅资料并熟悉ucore。查阅资料包括书籍的资料，主要是为了了解inode与vfs等，另外还发邮件询问了在xv6上做过和vfs、Fat32有关工作的学长。本周是第四周。
\item\emph{19th$\scriptsize{\sim}$25th March 2011} 进一步熟悉ucore，尤其是文件系统的框架。同时对shell做了一些尝试性的变动，如总是显示当前路径等。
\item\emph{26th March$\scriptsize{\sim}$1st April 2011} 设计ffs的框架，制作fat.img，开始尝试mount fat.img。
\item\emph{2nd$\scriptsize{\sim}$8th April 2011} 成功mount fat.img，其中还需要实现ffs\rule[-2pt]{1.5mm}{0.5pt}load\rule[-2pt]{1.5mm}{0.5pt}inode，因为在mount的时候需要获得根目录的inode，而此时就需要调用此函数。同时也实现了读磁盘函数，在diskio.c文件中。
\item\emph{9th$\scriptsize{\sim}$15th April 2011} 修改了FatFs库的参数MAX\rule[-2pt]{1.5mm}{0.5pt}SS，免掉了disk\rule[-2pt]{1.5mm}{0.5pt}ioctl函数的实现。同时修正了几个bug。
\item\emph{16th$\scriptsize{\sim}$22th April 2011} 小范围修改了框架，主要是几个工具函数的传参，实现了ffs\rule[-2pt]{1.5mm}{0.5pt}read等函数，最终成功加载了shell。
\item\emph{23th$\scriptsize{\sim}$29th April 2011} 遇到了一堆bug，主要是内存访问的地址发生了错误。尝试修补了一些bug，但是没有解决最关键的。这周几乎没有进展。
\item\emph{30th April$\scriptsize{\sim}$6th May 2011} 解决了内存访问时的错误，修正了几个返回值。详见第六个section的最后。
\item\emph{7th$\scriptsize{\sim}$13th May 2011} 这周实现了大量的函数，并成功运行了bin下的一堆测试程序。并成功进行了跨文件系统的读写。同时实现了用户程序cp等。
\item\emph{14th$\scriptsize{\sim}$20th May 2011} 完善了下cp指令，完善了wiki上的文档。
\item\emph{21th$\scriptsize{\sim}$27th May 2011} 给rm指令添加了-r参数。

\end{enumerate*}
	
\section{已有基础}
\subsection{ucore-vfs}
在我们展开工作之前，原有的ucore已经有vfs，并且该vfs能良好的支持ucore自带的文件系统sfs(simple filesystem)。此外还有一些参考资料。其中之一是哈佛的操作系统os161，虽然ucore的结构和os161不尽相同，但是它们的vfs的结构相似，并且os161有详尽的注释，利于我们对代码的理解。
每一个新加入的设备或者文件系统都需要针对vfs实现接口，例如sfs提供给vfs的文件操作接口如下：

\begin{tabular}{|c|c|}
\hline
需要的接口 & 对应的函数 \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}magic  & VOP\rule[-2pt]{1.5mm}{0.5pt}MAGIC \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}open   & sfs\rule[-2pt]{1.5mm}{0.5pt}openfile \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}close  & sfs\rule[-2pt]{1.5mm}{0.5pt}close \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}read   & sfs\rule[-2pt]{1.5mm}{0.5pt}read \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}write  & sfs\rule[-2pt]{1.5mm}{0.5pt}write \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}fstat  & sfs\rule[-2pt]{1.5mm}{0.5pt}fstat \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}fsync  & sfs\rule[-2pt]{1.5mm}{0.5pt}fsync \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}mkdir  & NULL\rule[-2pt]{1.5mm}{0.5pt}VOP\rule[-2pt]{1.5mm}{0.5pt}NOTDIR \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}rmdir  & NULL\rule[-2pt]{1.5mm}{0.5pt}VOP\rule[-2pt]{1.5mm}{0.5pt}NOTDIR \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}link   & NULL\rule[-2pt]{1.5mm}{0.5pt}VOP\rule[-2pt]{1.5mm}{0.5pt}NOTDIR \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}rename & NULL\rule[-2pt]{1.5mm}{0.5pt}VOP\rule[-2pt]{1.5mm}{0.5pt}NOTDIR \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}readlink & NULL\rule[-2pt]{1.5mm}{0.5pt}VOP\rule[-2pt]{1.5mm}{0.5pt}NOTDIR \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}symlink & NULL\rule[-2pt]{1.5mm}{0.5pt}VOP\rule[-2pt]{1.5mm}{0.5pt}NOTDIR \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}namefile   & NULL\rule[-2pt]{1.5mm}{0.5pt}VOP\rule[-2pt]{1.5mm}{0.5pt}NOTDIR \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}getdirentry & NULL\rule[-2pt]{1.5mm}{0.5pt}VOP\rule[-2pt]{1.5mm}{0.5pt}NOTDIR \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}reclaim & sfs\rule[-2pt]{1.5mm}{0.5pt}reclaim \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}ioctl  & NULL\rule[-2pt]{1.5mm}{0.5pt}VOP\rule[-2pt]{1.5mm}{0.5pt}INVAL \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}gettype & sfs\rule[-2pt]{1.5mm}{0.5pt}gettype \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}tryseek & sfs\rule[-2pt]{1.5mm}{0.5pt}tryseek \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}truncate   & sfs\rule[-2pt]{1.5mm}{0.5pt}truncfile \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}create & NULL\rule[-2pt]{1.5mm}{0.5pt}VOP\rule[-2pt]{1.5mm}{0.5pt}NOTDIR \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}unlink & NULL\rule[-2pt]{1.5mm}{0.5pt}VOP\rule[-2pt]{1.5mm}{0.5pt}NOTDIR \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}lookup & NULL\rule[-2pt]{1.5mm}{0.5pt}VOP\rule[-2pt]{1.5mm}{0.5pt}NOTDIR \\ \hline
.vop\rule[-2pt]{1.5mm}{0.5pt}lookup\rule[-2pt]{1.5mm}{0.5pt}parent  & NULL\rule[-2pt]{1.5mm}{0.5pt}VOP\rule[-2pt]{1.5mm}{0.5pt}NOTDIR \\ \hline
\end{tabular}

上述表格中，左边一列表示vfs需要的接口，而它的具体实现方法就是右边的函数。这里用函数指针的方法做到了类似面向对象语言中的多态。如果我们想添加FAT32，则就需要针对文件夹和文件都实现对应的接口。

\subsection{FatFs}
在对FAT32格式磁盘的读写访问上，网上已经有一个FatFs Generic File System Module。FatFs是一个通用的文件系统模块，用于在小型嵌入式系统中实现FAT文件系统。FatFs的编写遵循ANSI C，因此不依赖于硬件平台。它可以嵌入到便宜的微控制器中，8051、PIC、AVR、SH、Z80、H8、ARM等等。

FatFs具有如下特性
\begin{itemize*}
\item 支持与Windows兼容的FAT12，FAT16，与，FAT32；
\item 平台无关，封装良好；
\item 多种配置选项；
\item 支持多个卷(物理驱动器与分区)；
\item 支持多种扇区大小。
\end{itemize*}

FatFs提供了一些相关的函数，本次实验中用到的有：
\begin{itemize*}
\item\emph{f\rule[-2pt]{1.5mm}{0.5pt}mount} 接收磁盘驱动的编号以及一个FATFS*类型的结构，然后挂载fat.img。在本次实验中，第一个编号给0即可。
\item\emph{f\rule[-2pt]{1.5mm}{0.5pt}open} 接收一个FIL*类型结构，一个绝对路径名以及打开模式，如果模式是FA\rule[-2pt]{1.5mm}{0.5pt}READ，则打开文件后只有读权限，先要有写权限就需要传FA\rule[-2pt]{1.5mm}{0.5pt}WRITE，如果要创建新文件可以传FA\rule[-2pt]{1.5mm}{0.5pt}OPEN\rule[-2pt]{1.5mm}{0.5pt}ALWAYS，如果想同时有这3个权限则可以三者取或后传入。
\item\emph{f\rule[-2pt]{1.5mm}{0.5pt}close} 接收FIL*类型结构，关闭其指向的文件。
\item\emph{f\rule[-2pt]{1.5mm}{0.5pt}read} 接收FIL*类型结构，一个Buffer，一个数字表示想要读的字节数ByteToRead，以及另一个整形（按引用传）。然后会至多读FIL*对应的文件的ByteToRead个字节，存入到Buffer。具体读的字节数会存入到最后个参数返回。
\item\emph{f\rule[-2pt]{1.5mm}{0.5pt}lseek} 接收FIL*类型结构以及一个整形offset，移动指向文件起始位置的指针指第offset个字节。当读写文件不是从文件头开始时可以调用这个函数。
\item\emph{f\rule[-2pt]{1.5mm}{0.5pt}sync} 同步FIL中的数据。
\item\emph{f\rule[-2pt]{1.5mm}{0.5pt}opendir} 提供一个DIR*结构和绝对路径，打开文件夹后将信息存入到第一个参数。
\item\emph{f\rule[-2pt]{1.5mm}{0.5pt}readdir} 接收参数DIR*和FILINFO*，然后后一个参数中有一个成员fname，可通过它获得得到的文件名。这个函数使用方法类似一个迭代器，会逐次遍历文件夹中的所有项，全部遍历后返回NULL。
\item\emph{f\rule[-2pt]{1.5mm}{0.5pt}stat} 接收一个绝对路径的参数，以及一个FILINFO*，在本次实验中，调用这个函数后可以通过FILINFO*来判断绝对路径指向的是一个文件还是一个文件夹。
\item\emph{f\rule[-2pt]{1.5mm}{0.5pt}mkdir} 接收一个绝对路径，创建新文件夹。
\item\emph{f\rule[-2pt]{1.5mm}{0.5pt}unlink} 接收一个绝对路径，删除文件或文件夹。
\item\emph{f\rule[-2pt]{1.5mm}{0.5pt}rename} 接收一个OldName和一个NewName（都是char*类型），根据参数名和函数名就可以猜到这个函数的功能了。
\end{itemize*}

另外关于FatFs，还有几个接口需要实现，后面会再介绍。

\section{初识ucore}
\subsection{框架介绍}
我们的工作基于ucore的proj19展开。首先在kern/fs/文件夹下新增了fatfs文件夹，首先将FatFs库的源代码R0.08添加到导入到工程中。之后又针对vfs添加了相应的文件。如下只对需要自己添加代码的文件进行了介绍，这里需要说明的是，为了适应ucore，需要将ffconf.h文件中的\rule[-2pt]{1.5mm}{0.5pt}MAX\rule[-2pt]{1.5mm}{0.5pt}SS的值改为512，这个常数涉及到是否进行disk\rule[-2pt]{1.5mm}{0.5pt}ioctl操作，因为ucore中不需要该操作，所以按照代码中的注释，此处要把该常数赋值为512。

具体的框架如下图：

\includegraphics[width=40mm]{screenshot.png}

各个文件介绍如下：
\begin{itemize*}
\item\emph{/fatfs} 这个文件夹内的文件都是FatFs库的文件，且都已经完整实现。ff.h里面声明了一些提供给外界的接口，以及一些重要的struct，如FIL，DIR等。ff.c中包括了数据处理的一些函数，譬如大小写转换等。ffconf.h里面包括了一些基本的常数配置，如是否启用长文件名等，integer.h里面则包括了内置类型的定义。diskio.h则包括了一些磁盘读写的接口，以及一些常数的定义。

\item\emph{diskio.c} 这个文件提供了给FatFs库进行磁盘读写时的接口。不过由于ucore中已经有dev\rule[-2pt]{1.5mm}{0.5pt}disk0了，所以只用实现disk\rule[-2pt]{1.5mm}{0.5pt}read和disk\rule[-2pt]{1.5mm}{0.5pt}write即可。而这两个函数的实现可以参考kern/fs/devs/dev\rule[-2pt]{1.5mm}{0.5pt}disk0.c

\item\emph{ffs.h} 对FAT32文件系统的一些最为基本的定义，比如块大小等常量，这些都与原有的sfs类似，此处重点介绍下和sfs不同的地方。首先是FAT32是没有superblock的，虽然这个文件中也进行了定义，但实际上没有任何地方使用到它。然后是ffs\rule[-2pt]{1.5mm}{0.5pt}inode，因为FAT32原来是没有inode的，所以就需要人为的对它进行定义和赋值。为了实现的方便，我们去掉了原有的ino，即inode number。然后为了识别每一个特定的inode，我们在inode中添加了绝对路径的信息和父目录的inode的信息。其他方面与sfs类型类似。而在ffs\rule[-2pt]{1.5mm}{0.5pt}disk\rule[-2pt]{1.5mm}{0.5pt}inode中，因为已经不需要记录文件的位置等信息（因为有FatFs库），所以我们只需要记录此inode对应的文件或者文件夹的内存的指针即可。

\item\emph{ffs.c} 实现ffs\rule[-2pt]{1.3mm}{0.5pt}init函数即可。

\item\emph{ffs\rule[-2pt]{1.5mm}{0.5pt}fs.c} 此处重点是实现ffs\rule[-2pt]{1.5mm}{0.5pt}do\rule[-2pt]{1.5mm}{0.5pt}mount函数，调用f\rule[-2pt]{1.5mm}{0.5pt}mount函数即可，不过同时还要对inode\rule[-2pt]{1.5mm}{0.5pt}list等进行初始化。另外，几个用于对文件系统进行操作的接口也要实现，参考sfs即可。

\item\emph{ffs\rule[-2pt]{1.5mm}{0.5pt}inode.c} 这里是FAT32提供给vfs的接口，之后会再详细描述。
\end{itemize*}

此外，我还在kern/fs/dev/文件夹下添加了dev\rule[-2pt]{1.5mm}{0.5pt}disk1.c文件，然后把原有的fs.img设为disk1，新添的fat.img设为disk0。而ffs\rule[-2pt]{1.5mm}{0.5pt}lock.c并没有实际用处（可能因为我们关掉了swap）。

\subsection{inode与vfs初识}
在试图了解原有文件系统框架的时候，inode估计是最常碰到的数据结构之一了，并且在之后的工作中还要时刻和inode打交道，所以不能不对inode有一个大致的了解。

inode在一般的Unix风格的文件系统中都会存在，如UFS，Ext2等。一个inode往往对应一个文件或文件夹等，它存储了它所对应的文件或者文件夹的信息，包括类型、大小与位置等，同时包括关于此inode的信息，如编号等，但是并不包括文件数据和名字。一般磁盘上的第一个块（也可能是第0个块）会是一个叫superblock的块，它是用来统一管理所有的inode的，在这个块之后，存放的就是inode的相关的信息，如bitmap等（用来管理inode的分配），或者直接就存放了inode。在ucore中，bitmap的维护用bitmap.[ch]两个文件进行了统一的实现，便于sfs的调用。

但是如果磁盘上原来就没有inode的信息怎么办？譬如Fat32。但是vfs对inode的需求是统一的，即不管什么文件系统，在vfs看来都是有inode的。我个人理解这有点像面向对象语言里的多态。vfs就类似一个基类，或者是每个文件系统都需要实现的一个接口（类似Java中的interface），因此函数的参数都必须相同。而每一个文件系统就相当于它的一个派生类，或者说需要实现这个接口。vfs不涉及具体的实现细节，它只接收请求，然后再下放到具体的文件系统，由该文件系统返回后，vfs只取自己需要的返回信息（对每个文件系统的需求都是一样的）。因此，我们对Fat32就只能人为地构造inode，当然也完全可以不要superblock，既然vfs从来不需要它，而是我们通过另外的方法去维护Fat32的“inode”。

\subsection{从vfs到fatfs函数的具体调用过程}
下面举几个例子具体介绍从vfs下发出一个指令时操作系统是如何处理的。

因为有vfs，所以大部分对于文件系统的操作都是由vfs函数调用的。譬如当一个系统调用被触发时，可能就会调用一个名字类似vfs*.c的文件中的一个函数，譬如在sysfile.c里面的sysfile\rule[-2pt]{1.5mm}{0.5pt}rename函数就会调用vfs\rule[-2pt]{1.5mm}{0.5pt}rename，这是函数会对inode进行相应的维护，并同时在合适的情况下就会调用vop\rule[-2pt]{1.5mm}{0.5pt}rename，而vop\rule[-2pt]{1.5mm}{0.5pt}rename就是实际上的文件系统，譬如FAT32，或者sfs，提供给vfs的接口了。譬如在shell下提供的参数是FAT32文件系统中的文件，在ffs\rule[-2pt]{1.5mm}{0.5pt}inode.c最下面的ffs\rule[-2pt]{1.5mm}{0.5pt}node\rule[-2pt]{1.5mm}{0.5pt}fileops定义中我们可以看到vop\rule[-2pt]{1.5mm}{0.5pt}rename的定义就是ffs\rule[-2pt]{1.5mm}{0.5pt}rename，所以实际上vfs\rule[-2pt]{1.5mm}{0.5pt}rename就是会调用ffs\rule[-2pt]{1.5mm}{0.5pt}rename（如果提供的参数是FAT32中的文件的话）。

另外像read的系统调用会调用file.c中的file\rule[-2pt]{1.5mm}{0.5pt}read函数，而该函数也会调用vop\rule[-2pt]{1.5mm}{0.5pt}read，它的绑定和上面的vop\rule[-2pt]{1.5mm}{0.5pt}rename是类似的。不过这里的file\rule[-2pt]{1.5mm}{0.5pt}read更多涉及到文件操作，而不会做inode的信息的维护。

总之，就是在涉及到需要访问文件系统的信息时，譬如文件读写等，都是调用vop开头的函数，它又会根据实际情况具体判断是哪个文件系统的，以及参数的类型（文件还是文件夹等）来具体判断调用哪个函数。个人觉得其实现机制类似面向对象设计方法里面的多态。

\subsection{iobuf.[ch]介绍}
kern/fs/下的大部分文件只需要理解即可，而不必关心具体的成员的维护。但是iobuf在文件系统中也需要打交道，我对它的理解是提供了一个文件系统与其他结构（如内核等）的读写的缓冲区。如果有操作想往文件里写东西，就先写到iobuf里面，然后文件系统再向iobuf索取内容。而有操作需要读文件或者文件夹的信息时，文件系统也先写入到iobuf中，之后外界再通过它来获得内容。

iobuf中有4个成员，分别是io\rule[-2pt]{1.5mm}{0.5pt}base，它始终指想下一个未被使用的内存空间。所以在读写操作结束后，要对它的值（即指向的内存地址）做相应的维护。io\rule[-2pt]{1.5mm}{0.5pt}offset表示信息所在地址的偏移量。如果是读文件时，就表示从文件的第几个字节开始读，写的时候表示从第几个字节开始写。io\rule[-2pt]{1.5mm}{0.5pt}len一般表示待写的或者待读的字节数。而io\rule[-2pt]{1.5mm}{0.5pt}resid则表示实际读或者写完后剩余的字节数。可以通过io\rule[-2pt]{1.5mm}{0.5pt}resid是否为0来判断是否读写了规定的字节数。除io\rule[-2pt]{1.5mm}{0.5pt}len外另外3个成员都要在文件系统的函数里进行维护，具体维护的方法请参考下一个章节。

\section{ffs\rule[-2pt]{1.5mm}{0.5pt}inode.c实现详细介绍}
ffs\rule[-2pt]{1.5mm}{0.5pt}inode.c中是FAT32提供给vfs的接口，也是本次实验的重点所在，所以这里花一个章节来介绍此部分。该文件的实现过程可参考sfs\rule[-2pt]{1.5mm}{0.5pt}inode.c文件，而对一些具体的接口的功能如果有疑问，则可以参考os161中的注释。在具体实现过程中，由于FAT32的inode不同于sfs的inode，所以要维护好自己特有的一些信息。

首先介绍下ffs\rule[-2pt]{1.5mm}{0.5pt}inode以及ffs\rule[-2pt]{1.5mm}{0.5pt}disk\rule[-2pt]{1.5mm}{0.5pt}inode中不同于原有文件系统的部分。

由于FAT32是没有inode的，所以就需要我们自己构建inode。我参考原来的sfs\rule[-2pt]{1.5mm}{0.5pt}inode，创建了现在的ffs\rule[-2pt]{1.5mm}{0.5pt}inode如下：
\begin{lstlisting}
struct ffs_inode {
    struct ffs_disk_inode *din;
    uint32_t hashno;
	TCHAR* path;
	struct ffs_inode* parent;
	...
	struct ffs_inode_list* inode_link;
};
\end{lstlisting}

inode\rule[-2pt]{1.5mm}{0.5pt}link在sfs\rule[-2pt]{1.5mm}{0.5pt}inode中有类似的成员，其实就是保存所有已经创建的inode的一个链表。din之后再叙述。在sfs\rule[-2pt]{1.5mm}{0.5pt}inode中，会有一个ino，即inode number，来唯一标识每一个sfs\rule[-2pt]{1.5mm}{0.5pt}inode。而我们可以发现的是FatFs库很多函数都是直接需要绝对路径，而ffs\rule[-2pt]{1.5mm}{0.5pt}inode又是自己构建的，所以我决定直接用绝对路径来代替原来的ino。由于inode\rule[-2pt]{1.5mm}{0.5pt}link还需要索引inode，为了遍历时加快速度，我通过path计算了hashno。另外，parent是指向该文件或文件夹所在的父目录的ffs\rule[-2pt]{1.5mm}{0.5pt}inode，这是为了在查询的时候方便。

而ffs\rule[-2pt]{1.5mm}{0.5pt}disk\rule[-2pt]{1.5mm}{0.5pt}inode的结构（部分）如下
\begin{lstlisting}
struct ffs_disk_inode {
	...
	union {
		struct FIL* file;
		struct DIR* dir;
	} entity;
};
\end{lstlisting}
在原来的sfs\rule[-2pt]{1.5mm}{0.5pt}disk\rule[-2pt]{1.5mm}{0.5pt}inode中，会记录文件或文件夹在磁盘中的位置，但是这里我们有FatFs库了，所以无需那部分信息，只需要记录FatFs库需要的信息就可以了。在ffs\rule[-2pt]{1.5mm}{0.5pt}inode中我们已经记录了绝对路径，而这里我们就需要FIL或者DIR，即这个inode对应的文件或者文件夹的信息。

以上，ffs的inode就构建好了，接下来我们详细介绍ffs\rule[-2pt]{1.5mm}{0.5pt}inode.c中的函数。

我们可以将该文件中的函数按实现的方法分成如下六类：
\begin{itemize*}
\item\emph{6.1-6.5} 参照sfs相应函数，根据FAT32的不同做出相应的改变而实现;

\subsection{ffs\rule[-2pt]{1.5mm}{0.5pt}load\rule[-2pt]{1.5mm}{0.5pt}inode} 该函数通过相对路进path和父目录parent，计算出它们所对应的inode，并赋值在node\rule[-2pt]{1.5mm}{0.5pt}store中，如果不存在这样的inode，则创建一个新的inode。如果不能正常创建，则返回相应的错误。

ffs（表示FAT32文件系统）会存有一个ffs\rule[-2pt]{1.5mm}{0.5pt}inode\rule[-2pt]{1.5mm}{0.5pt}list，保存所有已经存在的inode。所以需要先通过lookup\rule[-2pt]{1.5mm}{0.5pt}ffs\rule[-2pt]{1.5mm}{0.5pt}nolock函数（该函数实现可参考sfs）从list中寻找。如果找不到就要新建一个inode。这里需要说明的是，在第一次调用该函数的时候，也就是在挂载文件系统的时候，此时其实并未完全挂载成功，不过可以通过检测path是否为根目录来做出相应的改变，如果是根目录直接当作文件夹来处理即可。

在创建新的inode的时候，需要在inode中保存其所对应的文件或者文件夹的绝对路径，此时可以通过getAbsolutePath计算绝对路径。

\subsection{ffs\rule[-2pt]{1.5mm}{0.5pt}getdirenty} 该函数返回文件夹中的文件或文件夹的名字。通过iob->io\rule[-2pt]{1.5mm}{0.5pt}offset来获得到底是需要第几个项的名字。如果不存在则返回异常。需要注意的是，尽管每一个文件名的长度可能不到512（即ffs\rule[-2pt]{1.5mm}{0.5pt}dentry\rule[-2pt]{1.5mm}{0.5pt}size）字节，但是iob->io\rule[-2pt]{1.5mm}{0.5pt}base还需要填满512字节，否则会返回异常。

\subsection{ffs\rule[-2pt]{1.5mm}{0.5pt}create} 创建新文件，如果文件本来就存在，则异常退出，否则就创建新文件。同样需要增加新的inode。

\subsection{ffs\rule[-2pt]{1.5mm}{0.5pt}lookup\rule[-2pt]{1.5mm}{0.5pt}once} 这个函数的功能是根据父节点和相对路径，此处的相对路径只有一层。来得到相应的inode。如果找不到文件则要返回-E\rule[-2pt]{1.5mm}{0.5pt}NOENT。

\subsection{lookup\rule[-2pt]{1.5mm}{0.5pt}ffs\rule[-2pt]{1.5mm}{0.5pt}nolock} 这个即在文件系统的inode\rule[-2pt]{1.5mm}{0.5pt}list里面去找是否已经有需要的inode，和原来的唯一不同之初即原来可以用接近O(1)的时间查找，而这里则是逐个查找。
\\
\item\emph{6.6-6.13} 参照sfs相应函数，调用FatFs库函数实现;

\subsection{ffs\rule[-2pt]{1.5mm}{0.5pt}openfile} 由于disk\rule[-2pt]{1.5mm}{0.5pt}inode的结构已经变化，所以可以根据需要在合适的地方调用f\rule[-2pt]{1.5mm}{0.5pt}open和f\rule[-2pt]{1.5mm}{0.5pt}close即可。因为这个原因，ffs\rule[-2pt]{1.5mm}{0.5pt}opendir和ffs\rule[-2pt]{1.5mm}{0.5pt}closedir就无需实现了，但是在读写文件的时候还涉及到权限，所以openfile还是需要实现，打开之后就会在相应的disk\rule[-2pt]{1.5mm}{0.5pt}node里面存有文件的信息了。

\subsection{ffs\rule[-2pt]{1.5mm}{0.5pt}opendir} 比openfile相对更加简单，只需要把得到的DIR的信息存入到相应的inode里面即可，而省略对权限的设置。

\subsection{ffs\rule[-2pt]{1.5mm}{0.5pt}close} 关闭文件，释放内存即可。

\subsection{ffs\rule[-2pt]{1.5mm}{0.5pt}read} 读取node所对应的文件的内容。读的起始地址是iob->io\rule[-2pt]{1.5mm}{0.5pt}offset，可以通过f\rule[-2pt]{1.5mm}{0.5pt}lseek函数来便宜文件指针的起始位置。读取的长度是iob->io\rule[-2pt]{1.5mm}{0.5pt}len，读取的内容存放到iob->io\rule[-2pt]{1.5mm}{0.5pt}base中。实际读取文件可以直接调用f\rule[-2pt]{1.5mm}{0.5pt}read函数。如果实际读取的字节数为rc，那么在读完后iob->io\rule[-2pt]{1.5mm}{0.5pt}base指向的地址和iob->io\rule[-2pt]{1.5mm}{0.5pt}offset的值都要加上rc，而iob->io\rule[-2pt]{1.5mm}{0.5pt}resid则要减去rc。

\subsection{ffs\rule[-2pt]{1.5mm}{0.5pt}write} 具体细节类似read，将iob->io\rule[-2pt]{1.5mm}{0.5pt}base中的内容写到node对应的FILE里面即可。

\subsection{ffs\rule[-2pt]{1.5mm}{0.5pt}mkdir} 因为有vfs的关系，所以不仅仅需要创建新的文件夹，还要为这个文件加创建相应的inode，然后加入到list当中。对inode的维护可以直接调用ffs\rule[-2pt]{1.5mm}{0.5pt}dirent\rule[-2pt]{1.5mm}{0.5pt}create\rule[-2pt]{1.5mm}{0.5pt}inode。

\subsection{ffs\rule[-2pt]{1.5mm}{0.5pt}rename} node和new\rule[-2pt]{1.5mm}{0.5pt}node分别对应旧和新的父目录的inode，此处同样需要维护好inode的信息。

\subsection{ffs\rule[-2pt]{1.5mm}{0.5pt}unlink} 删除已存在的文件，同时要删除相应的inode。
\\
\item\emph{6.14-6.17} 基本保留sfs中相应函数的原样;

\subsection{ffs\rule[-2pt]{1.5mm}{0.5pt}fstat} 返回node对应的状态，根据sfs实现即可。

\subsection{ffs\rule[-2pt]{1.5mm}{0.5pt}gettype} 返回类型，文件或文件夹。参照sfs即可。

\subsection{ffs\rule[-2pt]{1.5mm}{0.5pt}lookup} 根据inode和相对路径来获得相对路径所对应的inode，这里的相对路径可能是多层的。

\subsection{ffs\rule[-2pt]{1.5mm}{0.5pt}lookup\rule[-2pt]{1.5mm}{0.5pt}parent} 根据inode和相对路径来获得父目录的inode的信息。
\\
\item\emph{6.18-6.20} 根据函数的功能需要完全自己实现,而无法参考sfs的;

\subsection{ffs\rule[-2pt]{1.5mm}{0.5pt}dirent\rule[-2pt]{1.5mm}{0.5pt}search\rule[-2pt]{1.5mm}{0.5pt}nolcok} 查找文件中是否有名字为name的文件，如果有返回0，否则范围-E\rule[-2pt]{1.5mm}{0.5pt}NOENT。

\subsection{ffs\rule[-2pt]{1.5mm}{0.5pt}dirent\rule[-2pt]{1.5mm}{0.5pt}create\rule[-2pt]{1.5mm}{0.5pt}inode} 其功能与实现都类似ffs\rule[-2pt]{1.5mm}{0.5pt}load\rule[-2pt]{1.5mm}{0.5pt}inode在需要创建新的inode时所做的工作。它是供给mkdir和rename的时候使用的。

\subsection{ffs\rule[-2pt]{1.5mm}{0.5pt}namefile} 获得node对应文件的绝对路径，存到iob中。由于在inode里面本身就保存了绝对路径的信息，所以这部分的实现相对就变得比原来要简单一些了。直接进行字符串拷贝即可。
\\
\item\emph{6.21-6.23} 根据需要新添加的;

\subsection{findNode} 通过绝对路径找到已经存在的inode并返回。在rename里面需要得到旧的文件的信息，为了程序的结构化而单独实现。

\subsection{hash} 因为FAT32下的inode存放了绝对路径，而只根据绝对路径来匹配一个inode可能会需要耗费更多的时间，所以程序中根据绝对路径得到了一个hash值，计算hash的函数即为该函数。原来的文件系统会通过ino(inode number)类匹配一个inode。

\subsection{getAbsolutePath} 根据inode以及相对路径来计算绝对路径。因为在load\rule[-2pt]{1.5mm}{0.5pt}inode以及mkdir等多个函数里需要绝对路径，所以新增了这个函数。
\\
\item\emph{6.24-6.25} 无用而删除掉的;

\subsection{ffs\rule[-2pt]{1.5mm}{0.5pt}link} FAT32是没有硬连接的，所以无需关心此函数。

\subsection{ffs\rule[-2pt]{1.5mm}{0.5pt}reclaim} 释放inode，但是由于每一个inode都存放了父目录的inode，所以在这里并没有实现此函数。


另外还有ffs\rule[-2pt]{1.5mm}{0.5pt}tryseek，ffs\rule[-2pt]{1.5mm}{0.5pt}truncdir，ffs\rule[-2pt]{1.5mm}{0.5pt}truncfile。

\end{itemize*}


在实验中还需要注意的是，不要对空指针或没有有意义指向的指针进行kfree，不要对已经kfree过且未再使用过的指针进行kfree，否则会使内存分配出现异常。另外，函数的返回值必须符合规定，比如上面几处说到的返回-E\rule[-2pt]{1.5mm}{0.5pt}NOENT的地方等。否则也无法使程序正常运行。

\section{用户端新添加与完善过的指令}
\subsection{mount.c}
目前实现的其实并不是太完整，由于当前sh是从fs.img加载的，目前只能通过mount disk0 ffs来加载fat.img。不过和之后介绍的指令不同的是，添加一个mount.c需要增加一个系统调用。添加syscall的流程如下：先在user下添加mount.c，其中新添mount函数。mount函数的声明在user/libs下的dir.h下，实现在dir.c下。 在user/libs下的syscall.c和syscall.h下添加sys\rule[-2pt]{1.5mm}{0.5pt}mount函数的声明和实现。 在libs/unistd.h下添加SYS\rule[-2pt]{1.5mm}{0.5pt}mount的系统调用号。 在kern/syscall/syscall.c的最下面添加SYS\rule[-2pt]{1.5mm}{0.5pt}mount sys\rule[-2pt]{1.5mm}{0.5pt}mount一行，然后在上面添加sys\rule[-2pt]{1.5mm}{0.5pt}mount函数。 在kern/fs/sysfile下声明和实现sysfile\rule[-2pt]{1.5mm}{0.5pt}mount。然后这个实现过程就是做mount真正需要做的事情即可。

\subsection{cp.c}
复制程序，并且可以复制文件夹。不过复制文件夹是通过新建文件夹来实现的。同时还要保证在复制的时候提供正确的相对路径，否则会出现复制到错误的地方的状况。

\subsection{diff.c}
两个文件的比较，不断地读入并进行比较即可。

\subsection{grep.c}
字符串匹配，当初为了熟悉框架而实现的，在本次实验中作用比较鸡肋。

\subsection{mv.c}
目前只能移动文件，并且是通过读写而非硬连接的方法实现的。而查阅资料，Linux中的mv似乎是通过硬连接实现的。

\subsection{rm.c}
删除文件和文件夹，如果有-r参数，还能递归删除文件夹。

\subsection{sh.c}
原本的sh不会显示当前所在路径，需要pwd指令来获得。我让它目前会实时输出最新的所在路径。

\section{制作fat.img}
在Linux上可以通过如下办法制作一个64M的fat32格式的分区：
dd if=dev/zero of=disk.img count=131072
mkfs -t vfat -F 32 disk.img

然后挂载
sudo mount -o loop -t vfat disk.img /mnt

这样通过 /mnt 直接往里面灌文件。

拿u盘实验一下，抹掉数据：
sudo dd if=disk.img of=U盘

我试验了一下，F32挺成功。

\section{fat32的初始化}
因为增加了一个img，就需要在kern/fs/devs文件夹下增加dev\rule[-2pt]{1.5mm}{0.5pt}disk1.c，用来初始化新添加的磁盘，关于disk0与disk1和img的具体对应关系，可参加《修改Makefile》这个章节。dev\rule[-2pt]{1.5mm}{0.5pt}disk1.c的实现方法类似dev\rule[-2pt]{1.5mm}{0.5pt}disk0.c，只是对部分参数进行修改即可。同时，还要在fs.c的fs\rule[-2pt]{1.5mm}{0.5pt}init函数里面调用ffs\rule[-2pt]{1.5mm}{0.5pt}init()函数来初始化fat32文件系统。当前的shell是从fs.img加载的，如果想改成从fat.img加载，那可以在将proc.c文件里面init\rule[-2pt]{1.5mm}{0.5pt}main函数中的"disk1:"改成"disk0:"。

\section{修改Makefile}
为了将新加的代码文件也一同编译，需要对Makefile的KINCLUDE添加kern/fs/fatfs/和kern/fs/fatfs/fatfs/两项，对KSRCDIR添加kern/fs/fatfs和kern/fs/fatfs/fatfs两项。另外我又添加了backup文件夹，然后把fat.img放到该文件夹下，并在Makefile里添加如下：\\
\# create fat.img\\
FATIMG   := \$(call totarget,fat.img)\\
\$(FATIMG): \\
    \$(COPY) backup/fat.img bin/\\	

这样如果bin下没有fat.img，就会自动复制过去。

然后修改了QEMUOPTS如下：

QEMUOPTS = -hda \$(UCOREIMG) -drive file=\$(SWAPIMG),media=disk,cache=writeback -drive file=\$(FATIMG),media=disk,cache=writeback -drive file=\$(FSIMG),media=disk,cache=writeback

其实就是保留SWAPIMG为0号磁盘，然后让FATIMG为1号磁盘，FSIMG为2号磁盘。

\section{lib/string.c}
在文件系统中由于经常对字符串进行操作，我在lib/string.[ch]里增加了两个工具函数。一个是charInStr，用来判断一个特定的字符串是否有在一个字符串里出现，类似strchr函数。另一个函数是atoi函数，即将字符串转化为整数返回。

\section{测试}
因为只是新添加了文件系统，且目录结构相似，所以在文件系统内部进行测试时，原有针对sfs的测试都可以直接调用。我添加的测试代码只有一个cross\rule[-2pt]{1.5mm}{0.5pt}filetest1.c。它包括从sfs复制文件到fat32，再fat32复制文件到sfs，对新生成的文件均和原文件进行对比是否相同，确保相同之后将新生成的文件删除。主要是针对跨文件系统的读写进行测试。

\section{实验总结}
这个实验大约经历了十周的时间，从开始的对操作系统只有一个大致的了解，对文件系统和虚拟文件系统几乎一窍不通，到了现在，我也不敢说自己有多么了解。因为用了FatFs库的缘故吧，让我们实验的过程顺利了不少，尤其是后期开始真正实现vfs接口的时候。但即便如此，我们在实验过程中依旧遇到了许多不曾料到的困难。

操作系统作为软件，和我们以往实现的软件差别太大，因为它涉及到太多和硬件交互的问题。但是这方面我比较欠缺经验，这也是我当初选了这个题目的原因，觉得它毕竟还是比较偏软。

所谓万事开头难，这次实验亦不例外。不像其他做大实验的几位同学对Linux已经有长期的使用经验，以及对Linux内核的不少了解，我这方面知之甚少。在第四周和第五周刚接下题目的时候，感觉无从下手，只能到处找资料，但也焦急万分。第六周的时候任胜韦的几步工作终于让我们的工作有了大的进展，他的能力也的确很强。而实验到目前的阶段也和他初期的贡献是分不开的。

之后的每周都会有一些小的进展，尽管任胜韦被分配了其他的任务，但是他留下的框架其实比较容易懂，且mount函数是我和他一起实现的，所以我对他的思想也有了一定的了解。工作有条不紊地展开，直到第十周。

我记得第六周周末交流的时候，陈渝老师跟我说，估计我们的能力，大概能在第十周完成这个实验。之后由于我一个人在做了，所以我觉得如果能在十二周做出来的话，自己还是能够接受的。第八周过后我从每周五的下午就开始写实验，一直到周二上操作系统课前。所以在第十周的时候终于成功的让ucore读完了fat.img中的bin/sh并执行。之后遇到了严峻的问题，经常出现内存访问异常。

我其实并不是太清楚什么原因会导致这个问题，从log里面也没读出太多的信息。然后那一周就几乎毫无进展，也没有继续做下去的动力。五一也过得很不舒心，一直挂念着这件事。我最终只能硬着头皮尽量把代码彻底地过一遍，即便有可能导致小问题的地方我也都进行了修改。最终发现对同一个指针多次的kfree导致的这个问题。我觉得这体现操作系统体现的另一个特点是，编程人员要考虑很多安全性的问题。而不像直接使用库函数一样，它们已经相对比较健全。

这个bug让我印象非常深刻。同时让我觉得，实验中的耐心是非常必要的。可能很多地方只需要改动一两行的代码，就会有巨大的进展。

另外王乃铮的代码里很多使用的编程技巧都是我以前未曾见过的，这方面也有很多值得我学习的地方。

除这份文档之外，在google code上也有本项目，项目名字是u9proj，其中的wiki更为详细介绍了实验的一些细节。比如各周进展等。

\section{参考资料}
\begin{itemize*}
\item 《深入理解Linux内核》
\item 哈佛的教学用操作系统OS161
\item wikipedia上对于inode的介绍：http://en.wikipedia.org/wiki/Inode
\end{itemize*}

\section{致谢}
感谢陈渝老师和向勇老师在我实验过程中的耐心。我有几周的进展一度非常缓慢，不过得到了两位老师的谅解。还有两位老师对我实验过程中的支持以及资料的提供，特别是在刚开始的时候提供的入门的资料。所谓万事开头难，正是因为有那些资料，我们才能比较顺利地展开实验的过程。

还要感谢王乃铮学长的答疑，既包括第五周的那次对ucore整个框架的讲解，也包括整个学期对我们不停的提问的答疑，其中包括很多现在我们看来都非常简单的问题，以及对一些具体的类的介绍，比如iobuf等。还有些可能王乃铮学长也并不是记得太清楚了，就只能麻烦他又阅读了一遍代码。

此外，要感谢张旭学长、仇荣琦学长、匡冲学长对于我们初期的工作的建议，他们在xv6上做了和vfs以及FAT32相关的部分工作，所以给我们的建议也很有指导意义。

最后也感谢周边的同学以及其他参加大实验的同学在实验过程中和我展开的讨论，特别是任胜韦，尽管后期他参与到了其他的工作中，但是他在初期的贡献也是非常大的。
\end{document}
